package util.array;

/**
 * 给定两个一维int数组A和B.
 * 其中:A是长度为m、元素从小到大排好序的有序数组。B是长度为n、元素从小到大排好序的有序数组。希望从A和B数组中，找出最大的k个数字，要求:使用尽量少的比较次数。
 *
 * @author Liaorun
 */
public class FindKthMinNumber {

    public static void main(String[] args) {
        int res = findKthNum(new int[]{1, 2, 3}, new int[]{1, 2, 3, 4}, 1);

        System.out.println(res);
    }

    /**
     * 返回两个有序数组中第kth小的数
     *
     * @param arr1 数组1
     * @param arr2 数组2
     * @param kth  第几小
     * @return
     */
    public static int findKthNum(int[] arr1, int[] arr2, int kth) {
        if (arr1 == null || arr2 == null) {
            throw new RuntimeException("Your arr is invalid!");

        }

        if (kth < 1 || kth > arr1.length + arr2.length) {
            throw new RuntimeException("K is invalid!");
        }

        int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
        int[] shorts = arr1.length < arr2.length ? arr1 : arr2;

        int l = longs.length;
        int s = shorts.length;

        if (kth <= s) {
            return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
        } else if (kth > l) {

            // l < kth <= l + s
            // 手动排除两个值在调用算法
            if (shorts[kth - l - 1] >= longs[l - 1]) {
                return shorts[kth - l - 1];
            }

            if (longs[kth - s - 1] >= shorts[s - 1]) {
                return longs[kth - s - 1];
            }


            return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
        }
        // s < kth <= l 的情况
        if (longs[kth - s - 1] >= shorts[s - 1]) {
            return longs[kth - s - 1];
        }

        return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
    }

    /**
     * 返回两个等长度的有序数组的上中位数
     *
     * @param a1 数组1
     * @param s1 数组1的起始位置
     * @param e1 数组1的结束位置
     * @param a2 数组2
     * @param s2 数组2的起始位置
     * @param e2 数组2的结束位置
     * @return 上中位数
     */
    private static int getUpMedian(int[] a1, int s1, int e1, int[] a2, int s2, int e2) {
        int mid1 = 0;
        int mid2 = 0;
        int offset = 0;

        while (s1 < e1) {
            mid1 = (s1 + e1) / 2;
            mid2 = (s2 + e2) / 2;
            offset = (e1 - s1 + 1) & 1 ^ 1;

            if (a1[mid1] > a2[mid2]) {
                e1 = mid1;
                s2 = mid2 + offset;
            } else if (a1[mid1] < a2[mid2]) {
                s1 = mid1 + offset;
                e2 = mid2;
            } else {
                // 上中位数相等直接返回
                return a1[mid1];
            }
        }
        return Math.min(a1[s1], a2[s2]);
    }
}
